
package main.old.new_2023.last.month_8;


/**
 * @Description: todo 2337. 移动片段得到字符串
 * 给你两个字符串 start 和 target ，长度均为 n 。每个字符串 仅 由字符 'L'、'R' 和 '_' 组成，其中：
 * 字符 'L' 和 'R' 表示片段，其中片段 'L' 只有在其左侧直接存在一个 空位 时才能向 左 移动，而片段 'R' 只有在其右侧直接存在一个 空位 时才能向 右 移动。
 * 字符 '_' 表示可以被 任意 'L' 或 'R' 片段占据的空位。
 * 如果在移动字符串 start 中的片段任意次之后可以得到字符串 target ，返回 true ；否则，返回 false 。
 *
 * todo 1071. 字符串的最大公因子
 * 对于字符串 s 和 t，只有在 s = t + ... + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。
 * 给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 x 能除尽 str2 。
 *
 * todo 392. 判断子序列
 * 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
 * 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）
 * 进阶：
 * 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/
 * @Param:
 * @return:
 **/
public class Solution0821 {
    //判断子序列
    public boolean isSubsequence(String s, String t) {
        if (s.length() >t.length()){
            return false;
        }
        int i = 0,j = 0;
        //双指针
        for (;i<s.length() && j < t.length();i++){
            char temp = s.charAt(i);
            while (j < t.length()){
                if (t.charAt(j) == temp){
                    break;
                }
                j++;
            }
            j++;
        }
        if (j > t.length() || i+1  <= s.length()){
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Solution0821 test = new Solution0821();
        boolean subsequence = test.isSubsequence("acb", "ahbgdc");
        System.out.println(subsequence);
    }


    //字符串的最大公因子
    public String gcdOfStrings(String str1, String str2) {
        //如果有公因子 str1 + str2 = str2 +str1
        if (!(str1 + str2).equals(str2 +str1)){
            return "";
        }
        //辗转相除法 求出最大公因子
        int max = getMax(str1.length(), str2.length());
        return str1.substring(0,max);

    }
    //辗转相除法
    private static int getMax(int a,int b){
        if (b == 0){
            return a;
        }
        return getMax(b,a%b);
    }

    //移动片段得到字符串
    public boolean canChange(String start, String target) {
        if (start.length() == 0){
            return true;
        }
        if (start.length() != target.length()){
            return false;
        }
        if (!start.replaceAll("_","").equals(target.replaceAll("_",""))){
            return false;
        }
        //双指针判断
        for (int i=0,j = 0;i<start.length();i++){
            if (start.charAt(i) == '_') continue;
            while (target.charAt(j) == '_') {
               j++;
            }
            // 是 L 的话 ， i>j,因为 i只能左移
            if (start.charAt(i) == 'L' && i<j){
                return false;
            }
            if (start.charAt(i) == 'R' && i>j){
                return false;
            }
            j++;
        }
        return true;





    }

}
